// rsa.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "rsa.h"
#include <time.h>


const ulong n[] = {
	0x9bebbb80d92aeacb, 0xa4d1c50c3cb90d4, 0xe4e7e25452f7614, 0x7cc9ed9a765f73db,
	0xcda74149c6d68b4c, 0xe8098f53152a6e1a, 0x8093dd18a9a92d54, 0x15ec5fc2a0a828e2,
	0xe5177a98942bc34c, 0x3c827519ad52efe3, 0xcf2c93e82b953313, 0xf26995e04fac8397,
	0xa67c43e467d7e2c3, 0xadeb65d6ee0c1d71, 0x92b3b27fc92f3b26, 0xb59279afb2f7a7d3,
	0x3bcc26e2bb9ebb71, 0xab1863fb3ce40c8, 0xb5de6a7732e12542, 0x165caa7b91861a94,
	0x725be0b8ef25a5b9, 0x1966f40feea0d58e, 0x1dc65fbb0b82c902, 0x159ec68e4aff1b39,
	0x15530655f6e7ffbe, 0x61795655982ee535, 0x6425b6efd4f8b3da, 0x80a538fbea13bc7f,
	0x79dffe13ca43e033, 0x8af279f488d1c203, 0xce83e60e056a3f3e, 0xa4ae21de8f3735df };

const ulong d[] = {
	0xbe8e6815ac08f771, 0x441dd579f4618f00, 0x9687f5530d35fd40, 0xa3e1ad51cb3cc18a,
	0x97434839806420e7, 0xe9350a109d9fff0c, 0xd56c7ae8da978b6, 0x5bd53701884fac59,
	0x68d0415b75f7d4fd, 0x347a786169d52a44, 0x694175f39b0c209a, 0xa663f7567591651c,
	0x683f99238bb7d897, 0xeabc7d9197063eec, 0x5338b5f87168c867, 0xeded58e57c647b24,
	0x23a8610cfcea2a1a, 0x9c0c8a2128dae731, 0x1378b5d033092585, 0xa22e3d153cc5ac42,
	0x6dba863c07b73781, 0xb5ea05d90897d0a, 0x5a3217642b55b07b, 0xf3d058303cb2cc50,
	0xb9b8be7c721def88, 0xe983331defeafaec, 0x250c002dde41215f, 0xe0e0d46e3b65ed80,
	0x88cf132ab754df05, 0x3bae937b531f6837, 0xc64e92146d92eb10, 0xa2ab83b755dee2af };

const ulong e[] = { 0x10001 };

const ulong m[] = {
	0xb4b27ad703d4fa24, 0xd3c96bce64a17dce, 0x65ad5abcb8d02c38, 0xb5ebca1204b6350,
	0x61fb18548bd62301, 0x5bab7d4f64a7f35b, 0xbe226e7a22c691ff, 0x98b0cb35a79b7bbc,
	0x965158b69eecf1cf, 0xf1fb3c605c121a0e, 0x4d7c7b3260ed8ab, 0x8df7998ff8b804b5,
	0x905492f065bd19da, 0x4b9dde4196c78bf6, 0x8b8908ded78103a, 0x476327f0dbb8a456,
	0x3174e8136aeacd64, 0x2c26d599a96d03a8, 0x27c9105cf2fa85c7, 0x3e412f5c401d590e,
	0x736aac12037a248f, 0x2d903d61a4d990c0, 0x57482d4c5660680b, 0x8eabb75744ec4cab,
	0xa1dc2a1be4ee12d2, 0x22b54743cf247c9a, 0x4239ac666409c51c, 0xb690498a6225b2db,
	0xb9b4a7d25c7c94a, 0x3962f13fa5d6f845, 0xd10858486b39853a, 0x6376645a50609677 };

const ulong c[] = {
	0x476ee3e55362531b, 0x40046685e4a5a5e2, 0x8561bfa09d1fb094, 0x91c592439f0049b,
	0x840fd7dd5aab5393, 0x303c8b58c44c3f9, 0xa31150b5a2f22600, 0xe8846895cb2338e5,
	0x1fcc31b14435b329, 0xea82888850564064, 0x986686639f9cef69, 0x1182b15729e952e,
	0x6cdef231c4f961ac, 0x83dea5acd0d07ff2, 0xcce8b0e99196ccb3, 0xbd6f7aaeb41bb1d3,
	0x2f7dbe86a11b6ff2, 0x7ca8194e24c655f1, 0x74cb9837581c67a8, 0x11b7724f31faae18,
	0xb4b8a6893ac155d0, 0xed75d6052855ea6e, 0xe08d924cb7fd06b8, 0xb3eaf0af1d2e9dfd,
	0xadc4c7265ae5e788, 0xc2c989c1b36d9be4, 0xf3981127287f2c21, 0x229b47f6661e548a,
	0xe522f751b0da3347, 0x685b83795f46e1d1, 0x308353e3859cd058, 0x00020994a5fa579a };

vector_int array2vector(const ulong* p, int s)
{
	vector_int ret;
	while (s > 0)
	{
		ret.push_back(*p % mask);
		ret.push_back(*p / mask);
		s--;
		p++;
	}
	clear_leading_zero(ret);
	return ret;
}

vector_int operator*(const vector_int& l, const vector_int& r)
{
	vector_int ret(l.size()+r.size(), 0);
	for (int i = 0; i < l.size(); i++)
	{
		if (l[i] == 0)
			continue;

		for (int j = 0; j < r.size(); j++)
		{
			ulong result = l[i] * r[j];
			ret[i + j] += result;
		}
		adjust(ret);
	}
	clear_leading_zero(ret);
	VERIFY_MULTI(l, r, ret);
	return ret;
}



bool operator==(const vector_int& l, const int r)
{
	if (l.size() != 1)
		return false;
	else if (l[0] != r)
		return false;
	else
		return true;
}

bool operator!=(const vector_int& l, const int r)
{
	return !(l == r);
}

vector_int try_division(vector_int& a, const vector_int& b)
{
	int p = a.size() - 1;
	int q = b.size() - 1;
	ulong last_a = 0;
	while (p >= q)
	{
		last_a = last_a * mask + a[p];
		ulong tmp = last_a / b[q];
		while (tmp > 0)
		{
			vector_int X(p - q + 1, 0);
			X[p - q] += tmp;
			adjust(X);
			clear_leading_zero(X);
			vector_int delta = X * b;
			if (a > delta)
			{
				a = a - delta;
				return X;
			}
			tmp--;
		}
		p--;
	}
	return vector_int(1, 0); 
}

vector_int operator%(const vector_int& l, const vector_int& r)
{
	vector_int A = l;
	vector_int X(1, 0);
	vector_int newX(1, 0);
	do
	{
		newX = try_division(A, r);
		X = X + newX;
	}while (newX != 0);
	VERIFY_MOD(l, r, A, X);
	return A;
}

vector_int operator>>(const vector_int& l, int r)
{
	vector_int ret(l.size(), 0);
	ulong carray = 0;
	for (int i = l.size() - 1; i >= 0; i--)
	{
		ulong v = l[i];
		ret[i] = (v >> r) + carray;
		carray = (v & ((1 << r) - 1)) << (32 - r);
	}
	clear_leading_zero(ret);
	return ret;
}

vector_int operator<<(const vector_int& l, const int r)
{
	int off = r / 32;
	int delta = r % 32;
	vector_int ret(l.size() + off, 0);
	ulong carray = 0;
	for (int i = 0; i < l.size(); i++)
	{
		ulong v = (l[i] << delta);
		ret[i + off] = (v & 0xffffffff) | carray;
		carray = v >> 32;
	}
	if (carray > 0)
		ret.push_back(carray);
	return ret;
}

bool is_odd(const vector_int& l)
{
	return l[0] & 1;
}

void dump_hex(const vector_int& v)
{
	for (int i = 0; i < v.size(); i+=2)
	{
		ulong tmp = v[i];
		tmp += ((i + 1) < v.size() ? v[i + 1] : 0) * mask;
		printf("%016llx", tmp);
		if ((i % 8) == 6)
			printf("\n");
		else
			printf(",");
	}
	printf("\n");
}
vector_int calc_rsa_1(const vector_int& n, vector_int e, vector_int input, int off = 0)
{
	vector_int ret;
	//printf(">[%08d]%08x, %08x\n", off, e[0], input[0]);

	if (e == 1)
	{
		ret = input % n;
	}
	else if (!is_odd(e))
	{
		vector_int a = calc_rsa_1(n, e >> 1, input, off + 1);
		ret = (a * a) % n;
	}
	else
	{
		vector_int a = calc_rsa_1(n, e - vector_int(1, 1), input, off + 1);
		ret = (a * input) % n;
	}
	//printf("<[%08d]%08x\n", off, ret[0]);
	return ret;
}

vector_int calc_rsa_2(const vector_int& n, vector_int e, vector_int input)
{
	int max_bit = e.size() * 32 - 1;
	vector_int D(1, 1);
	while (max_bit >= 0)
	{
		D = D * D % n;
		if (bit_value(e, max_bit))
		{
			D = D * input % n;
		}
		//printf("%08x\n", D[0]);
		max_bit--;
	}
	return D;
}

int _tmain(int argc, _TCHAR* argv[])
{
	vector_int rsa_n = A2V(n);
	vector_int rsa_e = A2V(e);
	vector_int rsa_d = A2V(d);
	vector_int rsa_m = A2V(m);
	vector_int rsa_c = A2V(c);

	clock_t start = clock();
	vector_int rsa_result = calc_rsa_3(rsa_n, rsa_d, rsa_m);
	clock_t finish = clock() - start;
	printf("\n");
	dump_hex(rsa_result);
	printf("%f seconds elapsed\n", finish / (double)CLOCKS_PER_SEC);
	return 0;
}

